package week_five;

public class QuickSort {
    public int[] sortArray(int[] nums) {
        quickSort(nums, 0, nums.length - 1);
        return nums;
    }

    private void quickSort(int[] nums, int start, int end) {
        if (start >= end) return;
        int pivot = partition(nums, start, end);
        quickSort(nums, start, pivot);
        quickSort(nums, pivot + 1, end);
    }

    private int partition(int[] nums, int start, int end) {
        int p = start + (int) (Math.random() * (end - start + 1));
        int l = start, r = end;
        int pivot = nums[p];
        System.out.println("p: " + p + " pivot: " + pivot);
        while (l <= r) {
            while (nums[l] < pivot) l++;
            while (nums[r] > pivot) r--;
            System.out.println("l: " + l);
            System.out.println("r: " + r);
            if (l == r) break;
            if (l < r) {
                int temp = nums[l];
                nums[l] = nums[r];
                nums[r] = temp;
                l++;
                r--;
            }
        }
        return r;
    }


    public static void main(String[] args) {
        int[] res = new QuickSort().sortArray(new int[]{21, 4, 532, 5, 6, 23, 94, 6, 7});
        for (int i : res) {
            System.out.print(i + " ");
        }
    }
}
